#include <bits/stdc++.h>
using namespace std;

/*
1323. 6 和 9 组成的最大数字
已解答
简单
相关标签
premium lock icon
相关企业
提示
给你一个仅由数字 6 和 9 组成的正整数 num。

你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。

请返回你可以得到的最大数字。

 

示例 1：

输入：num = 9669
输出：9969
解释：
改变第一位数字可以得到 6669 。
改变第二位数字可以得到 9969 。
改变第三位数字可以得到 9699 。
改变第四位数字可以得到 9666 。
其中最大的数字是 9969 。
示例 2：

输入：num = 9996
输出：9999
解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。
示例 3：

输入：num = 9999
输出：9999
解释：无需改变就已经是最大的数字了。
 

提示：

1 <= num <= 10^4
num 每一位上的数字都是 6 或者 9 。
*/

// 法一
class Solution {
public:
    int maximum69Number (int num) {
        // 将数字转换为字符串，便于遍历和修改
        string s = to_string(num);
        
        // 从左到右遍历字符串，找到第一个'6'并将其改为'9'
        for (char &c : s) {
            if (c == '6') {
                c = '9';
                break;  // 只翻转一次，找到第一个就退出
            }
        }
        
        // 将修改后的字符串转换回整数并返回
        return stoi(s);
    }
};

// 法二
class Solution {
public:
    int maximum69Number (int num) {
        // 纯数字 计算权重
        int tmp = num;
        int highWeight = 1;     // 最高位
        // 数字位的权重
        while (tmp >= 10) {
            tmp /= 10;
            highWeight *= 10;
        }
        // 高位遍历检查 修改6
        tmp = num;
        while (highWeight > 0) {
            // cur pos numDig
            int curDig = (tmp / highWeight) % 10;
            if (curDig == 6)        return num + 3 * highWeight;

            highWeight /= 10;       // 权重递减到下一个检查位
        }
        return num;
    }
};

// 法三 位运算辅助判断
class Solution {
public:
    int maximum69Number (int num) {
        int temp = num;
        int weight = 1;
        // 计算最高位权重，使用位运算判断是否需要继续循环
        while ((temp / 10) > 0) {
            temp /= 10;
            weight *= 10;
        }
        temp = num;
        while (weight > 0) {
            // 提取当前位数字，使用位运算取余（虽然这里和普通取余效果一样）
            int digit = (temp / weight) % 10;
            
            // 使用位运算判断是否为6（6的二进制是110）
            if ((digit & 0x6) == 6) {  // 0x6是十六进制，二进制为110，与6的二进制一致
                return num + 3 * weight;
            }  
            weight /= 10;
            // 使用位运算右移替代除法（仅当权重是2的幂时效果相同，这里主要是演示思路）
            // 注意：十进制权重不是2的幂，实际效果不同，仅作思路展示
            // weight = weight >> 1; 
        }
        return num;
    }
};

// 法四 基于法二的常数剪枝
// 使用初始化列表{1000, 100, 10, 1}直接遍历权重
// 循环次数固定为 4 次（常数级），实际运行效率更高。

class Solution {
public:
    int maximum69Number (int num) {
        // 从最高位到最低位检查（针对int范围内的数字，最多4位）
        // 权重依次为1000、100、10、1
        for (int weight : {1000, 100, 10, 1}) {
            // 提取当前位的数字
            if ((num / weight) % 10 == 6) {
                // 找到第一个6，转为9（加3*权重）
                return num + 3 * weight;
            }
        }
        // 全为9则返回原数
        return num;
    }
};